package likou;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/14 06:46
 */
public class _1122 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(relativeSortArray(new int[]{2,3,1,3,2,4,6,7,9,2,19},new int[]{2,1,4,3,9,6})));
    }

    /**
     * 用了内置数据结构，4ms，超过30%
     * 不要一想到需求，就直接用内置数据结构，可以自定义数据结构！！
     * 内置数据结构虽然方便，但是很多操作都不是定制化操作，比较耗内存和时间！！
     * @param arr1
     * @param arr2
     * @return
     */
    public static int[] relativeSortArray(int[] arr1, int[] arr2) {
        Map<Integer,Integer> maps = new HashMap<>();

        for(int i=0;i<arr1.length;i++){
            maps.put(arr1[i],maps.getOrDefault(arr1[i],0)+1);
        }
        int index = 0;
        for(int i=0;i<arr2.length;i++){
            for(int j=0;j<maps.get(arr2[i]);j++){
                arr1[index] = arr2[i];
                index++;
            }
            maps.remove(arr2[i]);
        }
        List<Integer> collect = maps.keySet().stream().sorted().collect(Collectors.toList());
        for (int i=0;i<collect.size();i++){
            for (int j=0;j<maps.get(collect.get(i));j++){
                arr1[index] = collect.get(i);
                index++;
            }
            maps.remove(collect.get(i));
        }
        return arr1;
    }

    /**
     * 没用数据结构，0ms超过100%
     * @param arr1
     * @param arr2
     * @return
     */
    public int[] relativeSortArray2(int[] arr1, int[] arr2) {
        int[] count = new int[1001];

        int[] res = new int[arr1.length];

        for(int arr : arr1) count[arr]++;


        int idx = 0;
        for(int arr : arr2) {
            while(--count[arr] >= 0) {
                res[idx++] = arr;
            }
        }

        for(int i = 0; i < 1001; i++) {
            while(count[i] > 0) {
                res[idx++] = i;
                count[i]--;
            }
        }
        return res;
    }
}
